#include <vector>
#include <map>
#include <iostream>

using namespace std;

// 350
// 数组直接存入 map .  时间： O(nlogn) 空间： O(n)
class Intersect{
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
		// map 更新键值 这里当数组用 O(nlogn)
		map<int, int> record;
		for(int i = 0; i < nums1.size(); i++){
			record[nums1[i]]++;
		}
		// O(nlogn)
		vector<int> vectorResult;
		for(int i = 0; i < nums2.size(); i++){
			if(record[nums2[i]] > 0){
				vectorResult.push_back(nums2[i]);
				record[nums2[i]]--;
			}
		}

		return vectorResult;
	 
    }
};
